#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <stack>
#include<vector>
using namespace std;

struct Token {
    char type[20];
    char value[20];
    int line_number;
    int line_position;
};

// 自定义数据结构，isToken表示是否为终结符, val表示下标
struct Symbol{
    bool isToken;
    int val;
    Symbol(bool isToken1, int val1){
        isToken = isToken1;
        val = val1;
    }
};

//定义输入输出指针
FILE *fpr, *fpw;

//读入下一个Token,存入token，读完所有符号，返回null
Token nextToken() {
    Token token;
    strcpy(token.type, "\0");
    if(fpr != NULL){
        fscanf(fpr, "(%s , %s , %d , %d)\n", token.type, token.value, &token.line_number, &token.line_position);
        // if(fpw != NULL)
        //     fprintf(fpw, "(%s , %s , %d , %d)\n", token.type, token.value, token.line_number, token.line_position);
    }
    // cout << token.type << endl;
    return token;
}

//报错函数
void ERROR(char* value, int line, int position) {
    fprintf(fpw, "expected token: %s at line %d, position %d", value, line, position);
}

//终结符                0    1    2     3   4     5       6       7        8     9    10   11   12   13    14    15    16   17   18   19   20     21 
char input[22][10] = {"{", "}", "if", "(", ")", "then", "else", "while", "ID", "=", ";", "<", ">", "<=", ">=", "==", "+", "-", "*", "/", "NUM", "$"};

//非终结符                 0          1       2               3        4         5            6           7           8         9            10                11           12                13
char notFinal[14][20] = {"program", "stmt", "compoundstmt", "stmts", "ifstmt", "whilestmt", "assgstmt", "boolexpr", "boolop", "arithexpr", "arithexprprime", "multiexpr", "multiexprprime", "simpleexpr"};
vector<Symbol> table[14][22];

//录入预测分析表
void initTable(){

    // program -> compoundstmt
    table[0][0].push_back(Symbol(false, 2));

    //stmt ->  ifstmt  |  whilestmt  |  assgstmt  |  compoundstmt
    table[1][0].push_back(Symbol(false, 2));
    table[1][2].push_back(Symbol(false, 4));
    table[1][7].push_back(Symbol(false, 5));
    table[1][8].push_back(Symbol(false, 6));

    //compoundstmt ->  { stmts }
    table[2][0].push_back(Symbol(true, 0));
    table[2][0].push_back(Symbol(false, 3));
    table[2][0].push_back(Symbol(true, 1));
   
    //stmts ->  stmt stmts   |   $\varepsilon$
    table[3][0].push_back(Symbol(false, 1));
    table[3][0].push_back(Symbol(false, 3));
    table[3][1].push_back(Symbol(true, -1)); //以下标为-1的终结符视为空
    table[3][2].push_back(Symbol(false, 1));
    table[3][2].push_back(Symbol(false, 3));
    table[3][7].push_back(Symbol(false, 1));
    table[3][7].push_back(Symbol(false, 3));
    table[3][8].push_back(Symbol(false, 1));
    table[3][8].push_back(Symbol(false, 3));
    
    //ifstmt ->  if ( boolexpr ) then stmt else stmt
    table[4][2].push_back(Symbol(true, 2));
    table[4][2].push_back(Symbol(true, 3));
    table[4][2].push_back(Symbol(false, 7));
    table[4][2].push_back(Symbol(true, 4));
    table[4][2].push_back(Symbol(true, 5));
    table[4][2].push_back(Symbol(false, 1));
    table[4][2].push_back(Symbol(true, 6));
    table[4][2].push_back(Symbol(false, 1));
    
    //whilestmt ->  while ( boolexpr ) stmt
    table[5][7].push_back(Symbol(true, 7));
    table[5][7].push_back(Symbol(true, 3));
    table[5][7].push_back(Symbol(false, 7));
    table[5][7].push_back(Symbol(true, 4));
    table[5][7].push_back(Symbol(false, 1));
    
    //assgstmt -> ID = arithexpr ;
    table[6][8].push_back(Symbol(true, 8));
    table[6][8].push_back(Symbol(true, 9));
    table[6][8].push_back(Symbol(false, 9));
    table[6][8].push_back(Symbol(true, 10));

    //boolexpr  ->  arithexpr boolop arithexpr
    table[7][3].push_back(Symbol(false, 9));
    table[7][3].push_back(Symbol(false, 8));
    table[7][3].push_back(Symbol(false, 9));
    table[7][8].push_back(Symbol(false, 9));
    table[7][8].push_back(Symbol(false, 8));
    table[7][8].push_back(Symbol(false, 9));
   
    //boolop ->   <  |  >  |  <=  |  >=  | ==
    table[8][11].push_back(Symbol(true, 11));
    table[8][12].push_back(Symbol(true, 12));
    table[8][13].push_back(Symbol(true, 13));
    table[8][14].push_back(Symbol(true, 14));
    table[8][15].push_back(Symbol(true, 15));
   
    //arithexpr  ->  multexpr arithexprprime
    table[9][3].push_back(Symbol(false, 11));
    table[9][3].push_back(Symbol(false, 10));
    table[9][8].push_back(Symbol(false, 11));
    table[9][8].push_back(Symbol(false, 10));
    table[9][20].push_back(Symbol(false, 11));
    table[9][20].push_back(Symbol(false, 10));
   
    // arithexprprime ->  + multexpr arithexprprime  |  - multexpr arithexprprime  |   $\varepsilon$
    table[10][4].push_back(Symbol(true, -1));
    table[10][10].push_back(Symbol(true, -1));
    table[10][11].push_back(Symbol(true, -1));
    table[10][12].push_back(Symbol(true, -1));
    table[10][13].push_back(Symbol(true, -1));
    table[10][14].push_back(Symbol(true, -1));
    table[10][15].push_back(Symbol(true, -1));
    table[10][16].push_back(Symbol(true, 16));
    table[10][16].push_back(Symbol(false, 11));
    table[10][16].push_back(Symbol(false, 10));
    table[10][17].push_back(Symbol(true, 17));
    table[10][17].push_back(Symbol(false, 11));
    table[10][17].push_back(Symbol(false, 10));
    
    // multexpr ->  simpleexpr  multexprprime
    table[11][3].push_back(Symbol(false, 13));
    table[11][3].push_back(Symbol(false, 12));
    table[11][8].push_back(Symbol(false, 13));
    table[11][8].push_back(Symbol(false, 12));
    table[11][20].push_back(Symbol(false, 13));
    table[11][20].push_back(Symbol(false, 12));
    
    // multexprprime ->  * simpleexpr multexprprime  |  / simpleexpr multexprprime  |  $\varepsilon$
    table[12][4].push_back(Symbol(true, -1));
    table[12][10].push_back(Symbol(true, -1));
    table[12][11].push_back(Symbol(true, -1));
    table[12][12].push_back(Symbol(true, -1));
    table[12][13].push_back(Symbol(true, -1));
    table[12][14].push_back(Symbol(true, -1));
    table[12][15].push_back(Symbol(true, -1));
    table[12][16].push_back(Symbol(true, -1));
    table[12][17].push_back(Symbol(true, -1));
    table[12][18].push_back(Symbol(true, 18));
    table[12][18].push_back(Symbol(false, 13));
    table[12][18].push_back(Symbol(false, 12));
    table[12][19].push_back(Symbol(true, 19));
    table[12][19].push_back(Symbol(false, 13));
    table[12][19].push_back(Symbol(false, 12));
    
    // simpleexpr ->  ID  |  NUM  |  ( arithexpr )
    table[13][3].push_back(Symbol(true, 3));
    table[13][3].push_back(Symbol(false, 9));
    table[13][3].push_back(Symbol(true, 4));
    table[13][8].push_back(Symbol(true, 8));
    table[13][20].push_back(Symbol(true, 20));
}

//将token转为input数组中的下标
int tokenToInput(Token token){
    if(strcmp(token.type, "identifier") == 0)
        return 8;
    else if(strcmp(token.type, "number") == 0)
        return 20;
    else {
        for(int i = 0; i < 22; i++){
            if(strcmp(token.value, input[i]) == 0)
                return i;
        }
    }
    return -1;
}

int main() {
     //打开输入文件
    if ((fpr = fopen("../lexical_analysis/output/lexer_out.txt", "r")) == NULL) {  
        cout << "can't open this in file";
        exit(0);
    }
    // 打开输出文件
    if ((fpw = fopen("output/syntax_out.txt", "w+")) == NULL) {  
        cout << "can't open this out file";
        exit(0);
    }
    initTable();
    //读入第一个字符
    Token token;
    token = nextToken(); 
    stack<Symbol> s;
    s.push(Symbol(true, 21));
    s.push(Symbol(false, 0));  
    //非递归的预测分析法，教学视频：https://www.bilibili.com/video/BV1zW411t7YE?p=24
    while(strcmp(token.type, "") != 0 && !s.empty()){
        int token_sub = tokenToInput(token);
        Symbol symbol = s.top();
        s.pop();
        //栈顶为终结符，匹配判断
        if(symbol.isToken){
            if(token_sub == symbol.val){
                token = nextToken();
            }else{
                ERROR(input[symbol.val], token.line_number, token.line_position);
                exit(0);
            }
        } else{
            //栈顶为非终结符，查表
            vector<Symbol>symbols = table[symbol.val][token_sub];
            //表项为空，报错，打印所有期望的终结符
            if(symbols.empty()){
                string s;
                for(int i = 0; i < 22; i++){
                    if(!table[symbol.val][i].empty()){
                        s += input[i];
                        s += " ";
                    }
                }
                ERROR(&s[0], token.line_number, token.line_position);
                exit(0);
            }else{
                //表项不为空，打印产生式，并且将产生式右部符号压栈
                string ss = notFinal[symbol.val];
                ss += "->";
                for(int i = 0; i < symbols.size(); i++){
                    Symbol tem = symbols[i];
                    ss += " ";
                    ss += tem.isToken 
                        ? (tem.val != -1 ? input[tem.val] : "@")
                        : notFinal[tem.val];
                }
                fprintf(fpw, "%s\n", ss.c_str());   
                for(int i = symbols.size() - 1; i >= 0; i--){
                    if(symbols[i].val != -1)
                        s.push(symbols[i]);
                }
            }
        }
    }
}
